package a.面试;


import org.junit.Test;
import 其他.DataStructure.TreeNode;

public class Solution {
    class DNode{
        int val;
        DNode prep,next;
        DNode(int v){
            val=v;
        }
    }

    //--合并有序数组
    private int[] mergeOrderNums(int[] nums1, int[] nums2) {
        int n1=nums1.length, n2=nums2.length;
        int[] res = new int[n1+n2];//新空间
        int h1=0,h2=0,i=0;
        while(h1<n1&&h2<n2){
            if(nums1[h1]<=nums2[h2])res[i++]=nums1[h1++];
            else res[i++]=nums2[h2++];
        }

        if(h1==n1){
            for(int k=h2;k<n2;k++)res[i++]=nums2[k];
        }else if(h2==n2){
            for(int k=h1;k<n1;k++)res[i++]=nums1[k];
        }
        return res;
    }
    public boolean 是否是对称二叉树(TreeNode root) {
        if(root==null)return true;//特

        TreeNode h1 = root.left; TreeNode h2= root.right;
        if(h1==null||h2==null)return (h1==null)&&(h2==null); //单左分支斜着下来

        //后序
        return back(h1,h2);
    }
    public boolean back(TreeNode h1, TreeNode h2){
        //双空rTrue、一方空rFalse
        if(h1==null||h2==null){
            if(h1==null&&h2==null)return true;
            return false;
        }
        //从左下叶子开始向上return后序结果&&
        return (h1.val==h2.val) && back(h1.left,h2.right) && back(h1.right,h2.left);
    }


    public int getResult(int n, int m){
        DNode head = new DNode(1);
        DNode th = head;
        for (int i = 2; i <=n; i++) {
            DNode cur = new DNode(i);
            head.next=cur;
            cur.prep=head;
            head = head.next;
        }
        head.next=th;
        th.prep=head;

        int del = 0;
        DNode cn = th;
        while(true) {
            for (int i = 0; i < m-1; i++) {
                cn = cn.next;
            }
            delNode(cn);
            del++;
            if(del==n){
                break;
            }
        }
        return cn.val;
    }
    public void delNode(DNode c){
        DNode lf =c.prep;
        DNode rt =c.next;
        lf.next=rt; rt.prep=lf;
    }
}
